12.0 KB · ⇊ 9 parts · ⤓ Micron 12.0 KB · ⤓ HTML 57.8 KB

top

In number theory, the Kempner function S ( n ) {\displaystyle S(n)} cite-ref-oeis-1-0[1] is defined for a given positive integer n {\displaystyle n} to be the smallest number s {\displaystyle s} such that n {\displaystyle n} divides the factorial s ! {\displaystyle s!} . For example, the number 8 {\displaystyle 8} does not divide 1 ! {\displaystyle 1!} , 2 ! {\displaystyle 2!} , or 3 ! {\displaystyle 3!} , but does divide 4 ! {\displaystyle 4!} , so S ( 8 ) = 4 {\displaystyle S(8)=4} .

This function has the property that it has a highly inconsistent growth rate: it grows linearly on the prime numbers but only grows sublogarithmically at the factorial numbers.

• History

• Properties

• Computational complexity

• References and notes

This function was first considered by François Édouard Anatole Lucas in 1883,cite-ref-history1-2-0[2] followed by Joseph Jean Baptiste Neuberg in 1887.cite-ref-history2-3-0[3] In 1918, A. J. Kempner gave the first correct algorithm for computing S ( n ) {\displaystyle S(n)} .cite-ref-history3-4-0[4]

The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function in 1980.cite-ref-5[5]

Since n {\displaystyle n} divides n ! {\displaystyle n!} , S ( n ) {\displaystyle S(n)} is always at most n {\displaystyle n} . A number n {\displaystyle n} greater than 4 is a prime number if and only if S ( n ) = n {\displaystyle S(n)=n} .cite-ref-6[6] That is, the numbers n {\displaystyle n} for which S ( n ) {\displaystyle S(n)} is as large as possible relative to n {\displaystyle n} are the primes. In the other direction, the numbers for which S ( n ) {\displaystyle S(n)} is as small as possible are the factorials: S ( k ! ) = k {\displaystyle S(k!)=k} , for all k ≥ ≥ 1 {\displaystyle k\geq 1} .

S ( n ) {\displaystyle S(n)} is the smallest possible degree of a monic polynomial with integer coefficients, whose values over the integers are all divisible by n {\displaystyle n} .cite-ref-oeis-1-1[1] For instance, the fact that S ( 6 ) = 3 {\displaystyle S(6)=3} means that there is a cubic polynomial whose values are all zero modulo 6, for instance the polynomial x ( x − − 1 ) ( x − − 2 ) = x 3 − − 3 x 2 + 2 x , {\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,} but that all quadratic or linear polynomials (with leading coefficient one) are nonzero modulo 6 at some integers.

In one of the advanced problems in The American Mathematical Monthly, set in 1991 and solved in 1994, Paul Erdős pointed out that the function S ( n ) {\displaystyle S(n)} coincides with the largest prime factor of n {\displaystyle n} for "almost all" n {\displaystyle n} (in the sense that the asymptotic density of the set of exceptions is zero).cite-ref-7[7]

The Kempner function S ( n ) {\displaystyle S(n)} of an arbitrary number n {\displaystyle n} is the maximum, over the prime powers p e {\displaystyle p^{e}} dividing n {\displaystyle n} , of S ( p e ) {\displaystyle S(p^{e})} .cite-ref-history3-4-1[4] When n {\displaystyle n} is itself a prime power p e {\displaystyle p^{e}} , its Kempner function may be found in polynomial time by sequentially scanning the multiples of p {\displaystyle p} until finding the first one whose factorial contains enough multiples of p {\displaystyle p} . The same algorithm can be extended to any n {\displaystyle n} whose prime factorization is already known, by applying it separately to each prime power in the factorization and choosing the one that leads to the largest value.

For a number of the form n = p x {\displaystyle n=px} , where p {\displaystyle p} is prime and x {\displaystyle x} is less than p {\displaystyle p} , the Kempner function of n {\displaystyle n} is p {\displaystyle p} .cite-ref-history3-4-2[4] It follows from this that computing the Kempner function of a semiprime (a product of two primes) is computationally equivalent to finding its prime factorization, believed to be a difficult problem. More generally, whenever n {\displaystyle n} is a composite number, the greatest common divisor of S ( n ) {\displaystyle S(n)} and n {\displaystyle n} will necessarily be a nontrivial divisor of n {\displaystyle n} , allowing n {\displaystyle n} to be factored by repeated evaluations of the Kempner function. Therefore, computing the Kempner function can in general be no easier than factoring composite numbers.

cite-note-oeis-11. ↑ Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see citerefsloane-a002034Sloane, N. J. A. (ed.). "Sequence A002034 (Kempner numbers: smallest number m such that n divides m!)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

cite-note-history1-22. ↑ citereflucas1883Lucas, E. (1883). "Question Nr. 288". Mathesis. 3: 232.

cite-note-history2-33. ↑ citerefneuberg1887Neuberg, J. (1887). "Solutions de questions proposées, Question Nr. 288". Mathesis. 7: 68–69.

cite-note-history3-44. ↑ citerefkempner1918Kempner, A. J. (1918). "Miscellanea". The American Mathematical Monthly. 25 (5): 201–210. doi:10.2307/2972639. JSTOR 2972639.

cite-note-55. ↑ citerefhungerb-hlerspecker2006Hungerbühler, Norbert; Specker, Ernst (2006). "A generalization of the Smarandache function to several variables". Integers. 6: A23, 11. MR 2264838.

cite-note-66. ↑ citerefr-muller1990R. Muller (1990). "Editorial" (PDF). Smarandache Function Journal. 1: 1. ISBN 84-252-1918-3.

cite-note-77. ↑ citereferd-skastanas1994Erdős, Paul; Kastanas, Ilias (1994). "The smallest factorial that is a multiple of n (solution to problem 6674)" (PDF). The American Mathematical Monthly. 101: 179. doi:10.2307/2324376. JSTOR 2324376..